/*
 * @lc app=leetcode.cn id=556 lang=cpp
 *
 * [556] 下一个更大元素 III
 */

// @lc code=start
class Solution {
public:
    int nextGreaterElement(int n) {
        // 寻找下一个更大元素的标准做法，源自组合数学：
        // 从后往前搜索第一个降序数x；
        // 在这个序列里，找到比x大的第一个数y；
        // 交换x和y，将序列从小到大排序[reverse即可]
        string num = to_string(n);
        
        int i = num.size() - 1;
        while(i > 0 && num[i-1] >= num[i]) i--; //必须是>=，即找到第一个开始下降的数
        if(i == 0) return -1;
        i--;
        
        int j = num.size() - 1;
        while(num[j] <= num[i]) j--;    //必须是<=，即找到第一个绝对大的数
        
        swap(num[i], num[j]);
        
        reverse(num.begin() + i + 1, num.end());
        long long r = stoll(num);
        if(r > INT_MAX) return -1;
        return r;
    }
};
// @lc code=end

